n= 51618734558549353149468788156918294828938302985700710794432921580798232623308717832287009134888505878863695641658902807263863377913226965591301427914855149216674425459516306664577113484976761100176753594891847965202975659291216836705032178253649947618298873543018364965665144734971775778606006199177906284481
c1= 46627468058573565825078698251560707364435625205514932445873632376557580123804321000268341761594517585023307117341569436107609427613331807917934289571610709876634483935449700774355654604886095891877535098911963280361817747747039093226305441777391237584468304777919420025111888016319565636982838796394116412697
c2= 40908004756182884340620360712904135406447016440000976069353374341650658000157555328872344775396243430862514398746324836970780457517564182813232540513529009796723923796957542672081177739604358329303417899585554582406515034600341068744603221349575966321912919612384651713352458534286008196872716593210859446238

import libnum
import gmpy2

p1,s=gmpy2.iroot(n,4)
q=gmpy2.next_prime(p1)
p,s=gmpy2.iroot(n//(q*q),2)
print(n==p**2*q**2)

#解法1 共模攻击
s1,s2,gcd=libnum.xgcd(p,q)
m=pow(c1,s1,n)*pow(c2,s2,n)%n
print(libnum.n2s(int(m)))

#解法2 同余
phi=(p-1)*(q-1)
d=libnum.invmod(p,phi)
m=pow(c1,d,p*q)
print(libnum.n2s(int(m)))

#解法3 中国剩余
d1=libnum.invmod(p,p-1)
d2=libnum.invmod(q,q-1)
m1=pow(c1,d1,p)
m2=pow(c2,d2,q)
m=libnum.solve_crt([m1,m2],[p,q])
print(libnum.n2s(int(m)))